package datastructure.string;

/**
 *
 * @author Lei
 */
public class LongestPalindromicSubstring {

    /**
     * Dynamic programing method
     * 
     * @param inputString
     * @return 
     */
    public static void longestPalindromicSubstring(String inputString) {
        char[] chars = inputString.toCharArray();
        int[][] s = new int[inputString.length()][inputString.length()];
        int maxLength = 1;
        int maxStartIndex = 0;


        for (int m = 0; m < chars.length; m++) {
            s[m][m] = 1;
        }

        for (int n = 0; n < chars.length - 1; n++) {
            if (chars[n] == chars[n + 1]) {
                s[n][n + 1] = 1;
                maxLength = 2;
            }
        }

        for (int len = 3; len <= inputString.length(); len++) {
            for (int i = 0; i < inputString.length() - len + 1; i++) {
                int j = i + len - 1;
                if (chars[i] == chars[j] && s[i + 1][j - 1] == 1) {
                    s[i][j] = 1;
                    maxStartIndex = i;
                    maxLength = len;
                }
            }
        }
        
        System.out.println("the max length :" + maxLength);
        System.out.println("the string is : " + inputString.substring(maxStartIndex, maxStartIndex + maxLength));

    }

    public static void main(String[] args) {
        LongestPalindromicSubstring.longestPalindromicSubstring("FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth");

        //LongestPalindromicSubstring.longestPalindromicSubstring("cabdba");

    }
}
